package offer.algorithm;

import offer.singleLinkedList.Node;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/28 16:21
 */
public class ListMeetNode56 {

    public static <T> Node getMeetingNode(Node<T> head) {
        if (head == null || head.next == null)
            return null;
        Node slow = head,fast = head.next.next;
        while (slow != null && fast != null && fast != slow) {
            slow = slow.next;
            if (fast.next != null)
                fast = fast.next.next;
        }
        if (slow == null || fast == null)
            return null;
        slow = slow.next;
        int cycleNum = 1;
        while (fast != slow) {
            slow = slow.next;
            cycleNum++;
        }
        slow = fast = head;
        for (int i = 0; i < cycleNum; i++) {
            fast = fast.next;
        }
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

}
